package DP;

import sun.applet.Main;

/**
 * @Author: Gosin
 * @Date: 2020/5/27 16:34
 * 面积最大的正方形
 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 */
public class MaximalSquare {
    public static void main(String[] args) {
        MaximalSquare square = new MaximalSquare();
        char[][] s = {
                {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}
        };
        int i = square.maximalSquare(s);

        System.out.println(i);
    }
    public int maximalSquare(char[][] matrix) {
        //存在最优子结构的问题
        //int[][],设置二维数组，代表的是i,j,所能形成的矩阵的最大正方形的长度
        //f(i,j) = Min(Min(f(i-1,j),f(i,j-1)),f(i-1,j-1))+1
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxWidth=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    dp[i][j] = Integer.parseInt(String.valueOf(matrix[i][j]));
                    continue;
                }
                if(matrix[i][j] == '0'){
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                maxWidth = Math.max(maxWidth,dp[i][j]);
            }
        }
        return maxWidth*maxWidth;
    }

}
